package com.zj.leetcode.medium.binarySearch;

/**
 * @program: algorithm
 * @description: 分割等和子集
 * 416 partition-equal-subset-sum
 * @author: Zhang Bo
 * @create: 2022-05-12 14:03:51
 **/
public class PartitionEqualSubsetSum {
    public static void main(String[] args) {
        Solution solution = new PartitionEqualSubsetSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * [ 1 , 5 , 11 , 5 ]
         * 左边 > 右边  >
         * 左边 = 右边
         * 左边 < 右边
         * 0 1 12 13 2 23 3 123
         *
         * 音响 3000 4
         * 笔记本电脑 2000 3
         * 吉他 1500 1
         * iPhone 2000 1
         * @param nums
         * @return
         */
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }

            if (sum % 2 != 0) return false;
            int target = sum / 2;
            int[] dp = new int[target + 1];
            for (int i = 0; i < nums.length; i++) {
                for (int j = target; j >= nums[i]; j--) {

                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
            return dp[target] == target;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}